package 相同的树;

public class Solution {
    public boolean isSameTree(TreeNode p, TreeNode q) {
        // 使用递归方法
        // ① 参数：左树根节点，右树根节点。 返回值：boolean
        // ② 终止条件：p == null && q==null => true 或者 p==null||q==null => false
        // ③ 单层递归的逻辑：不断比较 左树的左孩子和右树的左孩子 以及 左树的右孩子和右树的右孩子
        if(p==null && q==null)
            return true;
        if(p==null || q==null)
            return false;
        // 左树的左孩子和右树的左孩子
        boolean outer = isSameTree(p.left, q.left);            // p:左  q:左
        // 左树的右孩子和右树的右孩子
        boolean inner = isSameTree(p.right, q.right);          // p:右  q:右
        // 最终结果需要外层和内层都比较成功，并且当前的根节点也要比较成功
        return p.val == q.val && outer && inner;               // p:中  q:中
    }
}
